Trong một chuyến đi Châu Đốc, Khánh Linh thấy đoàn hát An Giang thi tuyển diễn viên trẻ, anh định đăng ký chơi cho vui nào ngờ lại trúng tuyển, từ đây sự nghiệp của anh mới bước sang ngã rẽ. Ba năm phục vụ đoàn hát An Giang, anh được tập diễn từ vai hề trong các vở Sau ngày cưới và Sợi chỉ hồng, rồi dần dà lên kép nhì trong các vở Nước mắt Nùng Kha và Cành hoa xứ Thái, cuối cùng anh cũng được đóng thế kép chánh.[1]

Tiếp đó, anh được ông bầu Hai Néo mời về đoàn hát Tiếng Ca Sông Cửu chuyên đóng các vai trong tuồng dã sử và cổ tích, anh có dịp được cọ sát với nhiều tên tuổi lớn của sân khấu cải lương, nhờ vậy Khánh Linh dần nổi lên trong các chuyến lưu diễn khắp đồng bằng sông Cửu Long.

Năm 1986, Khánh Linh ký hợp đồng với đoàn Sông Hương ở Huế, thời gian này anh thường xuyên theo đoàn đi khắp các tỉnh Bắc Trung Bộ và Bắc Bộ, lúc này anh chuyển sang đóng các vai tuồng hương xa Ấn Độ.[3] Bấy giờ, Khánh Linh và Thiên Nga là hiện tượng, là cặp đôi sóng thần, họ làm mưa làm gió với vở diễn Tình yêu và nước mắt được chuyển thể và giàn dựng bởi quái kiệt Bo Bo Hoàng từ tác phẩm Mùa tôm của nhà văn Ấn Độ Thakazhi Sivasankara Pillai.[4]

Năm 1987, Khánh Linh trở về Miền Tây, anh được giao làm trưởng đoàn Cửu Long 2 đang vỡ nợ, anh tập hợp được nhiều nghệ sĩ tài năng và đổi tên thành đoàn hát Vĩnh Trà. Tuy doanh thu của đoàn cũng khá, nợ cũ của đoàn đều trả xong, nhưng vì công việc quản lý bận bịu suốt nên không có thì giờ để luyện tập ca hát và vũ đạo, Khánh Linh quyết định bàn giao lại đoàn hát cho sở văn hóa tỉnh, rồi anh lên Sài Gòn gia nhập đoàn hát của bầu Minh Tơ. Tại đây, Khánh Linh được nghệ sĩ Thanh Tòng đào đạo rất cơ bản tuồng Hồ Quảng nên tay nghề anh ngày càng điêu luyện, chuyên môn mỗi lúc được trau dồi thêm.

Năm 1991, đoàn Hương Mùa Thu thiếu kép, anh được mời sang diễn cùng nhiều tên tuổi lừng danh, thời gian này anh cũng phối hợp cộng tác với đoàn Trần Hữu Trang 2, hát chung với nghệ sĩ Cẩm Tiên trong một số vở.[5]